package com.yvon.service.demo.algorithm.offer;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * 数据流中的中位数
 */
public class P41 {

    public static void main(String[] args) {
        MedianFinder medianFinder = new P41().new MedianFinder();
        medianFinder.addNum(3);
        medianFinder.addNum(1);
        medianFinder.addNum(9);
        medianFinder.addNum(7);
        medianFinder.addNum(6);
        medianFinder.addNum(5);
        medianFinder.addNum(8);
        medianFinder.addNum(3);
        medianFinder.addNum(9);
        double median = medianFinder.findMedian();
        System.out.printf(String.valueOf(median));
    }




    /**
     * 创建大根堆、小根堆，其中：大根堆存放较小的一半元素，小根堆存放较大的一半元素。
     * 添加元素时，若两堆元素个数相等，放入小根堆（使得小根堆个数多 1）；若不等，放入大根堆（使得大小根堆元素个数相等）
     * 取中位数时，若两堆元素个数相等，取两堆顶求平均值；若不等，取小根堆堆顶。
     */
    class MedianFinder {
        Queue<Integer> minHeap;
        Queue<Integer> maxHeap;

        public MedianFinder() {
            minHeap = new PriorityQueue<>();
            maxHeap = new PriorityQueue<>((a, b) -> b - a);
        }

        public void addNum(int num) {
            if (maxHeap.size() ==minHeap.size()) {
                maxHeap.offer(num);
                // 放入小根堆(小根堆多1)
                minHeap.offer(maxHeap.poll());
            }else {
                minHeap.offer(num);
                // 放入大根堆(大小堆数量相等)
                maxHeap.offer(minHeap.poll());
            }
        }

        public double findMedian() {
            if (((maxHeap.size() + minHeap.size()) & 1) == 0) {
                return (maxHeap.peek() + minHeap.peek()) / 2.0;
            }else {
                return minHeap.peek();
            }
        }


    }
}
